package DummyHeadLinkedList;

class LinkedList<E> {

    private class Node {
        public E e;
        public Node next;

        public Node(E e, Node next) {

            this.e = e;
            this.next = next;
        }

        public Node() {
            this(null, null);
        }

        public Node(E e) {
            this(e, null);
        }

        @Override
        public String toString() {
            return e.toString();
        }
    }

    private Node head;
    private int size;

    private Node dummyHead;

    public LinkedList() {
        dummyHead = new Node();

        size = 0;
    }

    public int getSize() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    //在链表头增加元素,如果不理解可以想象将666这个元素放入0 1 2 这个链表里
    public void addFirst(E e) {
        //先new出来一个节点，
       // Node node = new Node(e);
        //node.next = head;//将新的元素的next指向目前的head
        //然后把新的head赋值给这个new出来的新node
        //head = node;
        //以上三句可以简化为 head=new Node(e,head)
        //size++;
        add(0,e);
    }

    //在链表中间增加元素
    public void add(int index, E e) {
        if (index < 0 || index > size) {//注意这里index是可以取到size的，代表从链表末尾添加一个元素
            throw new IllegalArgumentException("add failed,illegal index");
        }

        //对特殊链表在0位置的处理，加入dummyHead之后，实际链表的第一个元素是dummyHead的next元素，其中dummyHead的e为null
        Node prev = dummyHead;//用户对这个节点无感。这是为了找前一个节点用的
        for (int i = 0; i < index; i++) {
            prev = prev.next;
        }
        Node node = new Node(e);
        //找到node之前的元素prev,把prev.next指向666
        node.next = prev.next;
        prev.next = node;
        //prev.next=new Node(e,prev.next);这句话可以代替以上三句
        size++;
    }

    public void addLast(E e) {
        add(size, e);
    }


    public E get(int index) {
        if (index < 0 || index >= size) {//查找的时候根据索引，索引是小于size的,所以=不行
            throw new IllegalArgumentException("get failed,illegal index");
        }

        Node current = dummyHead.next;
        //移动这个指针
        for (int i = 0; i < index; i++) {
            current = current.next;
        }
        return current.e;
    }

    public void set(int index, E e) {
        if (index < 0 || index >= size) {//查找的时候根据索引，索引是小于size的,所以=不行
            throw new IllegalArgumentException("set failed,illegal index");
        }

        Node current = dummyHead.next;//这里找的是第一个元素（不包括dummyHead）
        //移动这个指针
        for (int i = 0; i < index; i++) {
            current = current.next;
        }
        current.e = e;
    }

    public boolean contains(E e) {

        Node cur = dummyHead.next;

        while (cur != null) {
            if (cur.e == e) {
                return true;
            } else {
                cur = cur.next;
            }
        }
        return false;
    }

    public void remove (E e){

        //找到要删除元素之前的那个元素，del，让del元素之前的next指向del之后的那个元素。让del的next指向null

        Node prev=dummyHead;

        while (prev.next!=null){
            if(prev.next.e.equals(e)){
                break;
            }else{
                prev=prev.next;
            }
        }

        if(prev.next!=null){
            Node delNode=prev.next;
            prev.next=delNode.next;
            delNode.next=null;//方便java的内存回收
            size--;
        }

    }

    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        //因为对链表尺寸未知，所以这里用while循环好一点
        //Node cur = dummyHead.next;
        //while (cur != null) {
        //    res.append(cur + "->");
        //    cur=cur.next;
        //}

        //以上的while可以这么写

        for (Node cur = dummyHead.next; cur != null; cur = cur.next) {
            res.append(cur + "->");
        }
        res.append("NULL");
        return res.toString();
    }

    public static void main(String[] args) {
        LinkedList<Integer> linkedList =new LinkedList <>();
        for (int i = 0; i <5 ; i++) {
            linkedList.addFirst(i);
            System.out.println(linkedList);
        }
        linkedList.add(2,666);
        linkedList.add(2,777);
        System.out.println(linkedList);
        linkedList.remove(777);
        System.out.println(linkedList);
        linkedList.remove(7779);
        System.out.println(linkedList);
        //java变量引用的概念，可以对比指针的概念
    }
}
